package mosdi.util.iterators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

import mosdi.matching.HorspoolMatcher;
import mosdi.matching.Matcher;

/** For a given list of sequences, this class enumerates all contained segments
 *  delimited by a given pattern (on both sides). The segments are ordered
 *  by their length (ascending). */
public class SegmentIterator implements Iterator<SegmentIterator.Segment> {
	private int patternLength;
	private List<int[]> strings;
	/** For each item of list "strings", this list stores an array of start positions
	 *  of the pattern. */
	private List<int[]> occurrences;
	/** If an integer weight was given for each occurrence, then this list contains
	 *  the cumulative weights, i.e. cumulativeWeights.get(j)[k] contains the sum 
	 *  of weights for occurrences.get(j)[0] to occurrences.get(0)[k] (inclusively). 
	 *  Null if no weights were given. */
	private List<int[]> cumulativeWeights;
	private PriorityQueue<SegmentIterator.Segment> queue;
	
	public class Segment implements Comparable<Segment> {
		private int stringIndex;
		// from and to refer to occurrences.get(segment)[from/to]
		private int from;
		private int to;
		private Segment(int stringIndex, int from, int to) {
			this.stringIndex = stringIndex;
			this.from = from;
			this.to = to;
		}
		/** Copy constructor. */
		public Segment(Segment segment) {
			this.stringIndex = segment.stringIndex;
			this.from = segment.from;
			this.to = segment.to;
		}
		public int[] getSegment() {
			return Arrays.copyOfRange(strings.get(stringIndex), getStartPosition(), getEndPosition());
		}
		public int length() { 
			return getEndPosition() - getStartPosition();
		}
		/** Returns the index of the string the segment stems from. */
		public int getStringIndex() { 
			return stringIndex;
		}
		/** Segments start position (inclusively). */
		public int getStartPosition() {
			return occurrences.get(stringIndex)[from];
		}
		/** Segments end position (exclusively). */
		public int getEndPosition() {
			return occurrences.get(stringIndex)[to] + patternLength;
		}
		/** The index of the pattern occurrence this segment starts at, i.e. if n is returned, then
		 *  the segment starts at (and includes) the n-th pattern occurrence. */
		public int getStartIndex() {
			return from;
		}
		/** The index of the pattern occurrence this segment ends at, i.e. if n is returned, then
		 *  the segment ends at (and includes) the n-th pattern occurrence. */
		public int getEndIndex() {
			return to;
		}
		/** The number of pattern occurrences in this segment, if weights were specified on
		 *  construction of SegmentIterator, the sum of weights of pattern occurrences is given. */
		public int getPatternCount() { 
			if (cumulativeWeights == null) {
				return to - from + 1;
			} else {
				if (from>0) {
					return cumulativeWeights.get(stringIndex)[to] - cumulativeWeights.get(stringIndex)[from-1]; 
				} else {
					return cumulativeWeights.get(stringIndex)[to];
				}
			}
		}
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Segment)) return false;
			return compareTo((Segment)obj) == 0;
		}
		@Override
		public int compareTo(Segment o) {
			if (length()<o.length()) return -1;
			if (length()>o.length()) return 1;
			if (stringIndex<o.stringIndex) return -1;
			if (stringIndex>o.stringIndex) return 1;
			if (from<o.from) return -1;
			if (from>o.from) return 1;
			return 0;
		}
		@Override
		public String toString() {
			return String.format("(%d: %d..%d)", stringIndex, from, to);
		}
		
	}

	
	public SegmentIterator(int alphabetSize, List<int[]> strings, int[] pattern) {
		super();
		this.patternLength = pattern.length;
		this.strings = strings;
		occurrences = new ArrayList<int[]>(strings.size());
		Matcher m = new HorspoolMatcher(alphabetSize, pattern);
		for (int[] s : strings) {
			occurrences.add(m.findAllMatchPositions(s));
		}
		initQueue();
	}
	
	/** Constructor.
	 * 
	 * @param patternLength Length of pattern whose start positions are listed in patternOccurrences.
	 * @param patternOccurrences For each entry in strings, this list gives an array of start positions
	 *                           of patterns delimiting the returned segments. NOTE: The segments are assumed
	 *                           to be sorted, if not behavior is undefined.
	 */
	public SegmentIterator(int alphabetSize, List<int[]> strings,  int patternLength, List<int[]> patternOccurrences) {
		this(alphabetSize, strings, patternLength, patternOccurrences, null);
	}

	/** Constructor.
	 * 
	 * @param patternLength Length of pattern whose start positions are listed in patternOccurrences.
	 * @param patternOccurrences For each entry in strings, this list gives an array of start positions
	 *                           of patterns delimiting the returned segments. NOTE: The segments are assumed
	 *                           to be sorted, if not behavior is undefined.
	 */
	public SegmentIterator(int alphabetSize, List<int[]> strings,  int patternLength, List<int[]> patternOccurrences, List<int[]> occurrencesWeights) {
		super();
		this.patternLength = patternLength;
		this.strings = strings;
		this.occurrences =  patternOccurrences;
		if (occurrencesWeights!=null) {
			if (occurrencesWeights.size()!=occurrences.size()) throw new IllegalArgumentException();
			cumulativeWeights = new ArrayList<int[]>(occurrences.size());
			for (int[] weights : occurrencesWeights) {
				int[] cWeights = new int[weights.length];
				for (int i=0; i<cWeights.length; ++i) {
					cWeights[i] = weights[i] + (i>0?cWeights[i-1]:0);
				}
				cumulativeWeights.add(cWeights);
			}
		}
		initQueue();
	}

	private void initQueue() {
		queue = new PriorityQueue<Segment>();
		for (int i=0; i<this.strings.size(); ++i) {
			for (int j=0; j<occurrences.get(i).length-1; ++j) {
				queue.add(new Segment(i,j,j+1));
			}
		}
	}

	@Override
	public boolean hasNext() {
		return !queue.isEmpty();
	}

	@Override
	public Segment next() {
		if (queue.isEmpty()) throw new NoSuchElementException();
		Segment segment = queue.remove();
		int[] o = occurrences.get(segment.stringIndex);
		if (segment.to+1<o.length) {
			queue.add(new Segment(segment.stringIndex, segment.from, segment.to+1));
		}
		return segment;
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

	
}
